1. Field of the Invention
The present invention relates to error detection and/or correction codes.
Error detection codes have a technical effect and solve a significant technical problem. Indeed, they enable restoring the value of one or several erroneous bits, for example, after a storage or a transmission. Without such codes, any storage or transmission of digital data would be difficult.
The present invention relates in particular to linear codes of Hamming type.
2. Discussion of the Related Art
The Hamming code is an error detection and correction code used in many fields. A first example of a Hamming code and its use for the data storage in a memory will be described, in the case where the data to be stored are in the form of 16-bit words.
Let X be the word to be stored. X may be represented by a vector Xe, the 16 components X0 to X15 of which correspond to the 16 bits of the word to be stored. Five error detection bits C1 (C0. . . C4) are obtained by multiplying a parity control matrix H, called a Hamming matrix, of dimensions 5×16, by vector Xe in the form of a column vector.
FIG. 1A illustrates Hamming matrix H for 16 bits and FIG. 1B illustrates the way to obtain the detection bits. Calling hij the elements of matrix H, the error detection bits C1 are given by:
      C    i    =            ∑              j        =        0            15        ⁢                  h        ij            ·              X        j            
Xj being the j-th component of vector Xe.
In write mode, 21-bit words, formed of the 16 data bits Xj and of the 5 detection bits C1, are written into the memory. In read mode, the read word includes 16 bits Xr corresponding to the data bits and 5 bits Cr corresponding to the detection bits. It is possible for Xr and Cr not to be equal to Xj and Ci if errors have occurred between the write and read operations.
To detect and/or correct possible errors on the read bits, a syndrome S with five components S0, . . . S4 is calculated by multiplying a determined matrix H′ of dimensions 5×21 by a column vector with 21 components, including the 16 bits Xr and the 5 bits Cr.
FIG. 2A illustrates matrix H′. The first 16 columns of matrix H′ correspond to the 16 columns of matrix H. The 5 following columns each include a single “1”. The 17-th column has its “1” on the first line, the 18-th column has its “1” on the second line, and so on until the 21rst column, which has its “1” on the fifth line. The last five columns of matrix H′ are used to determine possible errors in the detection bits.
FIG. 2B illustrates the calculation of syndrome S.
If syndrome S has all its components equal to 0, the storage occurs with no error and all the bits of the read word, be they data bits or detection bits, are correct.
If S is different from 0, the read word includes one or several errors. If a single bit of the read word is erroneous, the obtained syndrome enables correcting the error. Indeed, the syndrome corresponds in this case to the column having had its elements multiplied by the erroneous bit. Thus, if the calculated syndrome is equal to:
      S    =          (                                    0                                                0                                                0                                                1                                                1                              )        ,
the components (00011) of the syndrome correspond to the elements of the first column of the Hamming matrix, which means that the first bit, X0, is erroneous.
Similarly, if the calculated syndrome is equal to:
            S      ″        =          (                                    1                                                0                                                0                                                0                                                0                              )        ,
and there is a single error in the read word, this means that the first detection bit C0 is erroneous.
Since the above code cannot detect two errors, it is generally transformed by adding to the word to be coded a total parity bit P.
Total parity bit P is calculated by adding modulo 2 all the data bits and all the detection bits. The total parity bit is added to the word to be stored, and the coded word, that is, the word to be stored, the detection bits, and the total parity bit are altogether stored.
In read mode, the read word is multiplied by parity control matrix H″ shown in FIG. 3A. Matrix H″ has one more line and one more column than matrix H′. Matrix H″ includes, to the top left, that is, on the first five lines and on the first 21 columns, a block identical to matrix H′. The last line D of matrix H″ only includes “1s” and the last line of matrix H″ only includes “0s”, except for the last line.
The obtained syndrome S′ is illustrated in FIG. 3B. Syndrome S′ includes six components S0 to S5, and is obtained by multiplying matrix H″ by a column vector including the 22 bits of the read word, comprised of the 16 read data bits Xr, followed by the five read detection bits Cr, and by the read total parity bit Pr.
This second code is of the “SEC-DED” type (“Single Error Correction”—“Double Error Detection”). It can detect two errors in all cases, two errors being indicated by the fact that the last component of the syndrome, S5, is zero while the syndrome is different from the zero vector.
The detection bits and the total parity bit are calculated by a coding circuit, and the syndrome components are calculated by a decoding circuit. These circuits include a great number of elementary adders modulo 2. Since each elementary adder requires some time to perform an addition, the results provided by the coding and decoding circuits exhibit a given delay. It is desirable to reduce this delay. Further, prior art adders are relatively small and their realization, which is not optimal, do not enable them to be fast.